#include <bits/stdc++.h>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    int count;

    TrieNode() : count(0) {}
};

class Solution {
public:
    vector<int> longestCommonPrefix(vector<string>& words, int k) {
        TrieNode* root = new TrieNode();
        for (const string& word : words) {
            TrieNode* node = root;
            for (char c : word) {
                if (!node->children.count(c)) {
                    node->children[c] = new TrieNode();
                }
                node = node->children[c];
                node->count++;
            }
        }

        int n = words.size();
        vector<int> answer(n, 0);

        for (int i = 0; i < n; ++i) {
            if ((n - 1) < k) {
                answer[i] = 0;
                continue;
            }

            string word = words[i];
            vector<TrieNode*> path;
            TrieNode* node = root;
            bool valid = true;
            for (char c : word) {
                if (!node->children.count(c)) {
                    valid = false;
                    break;
                }
                node = node->children[c];
                path.push_back(node);
            }

            if (!valid) {
                answer[i] = 0;
                continue;
            }

            for (TrieNode* node : path) {
                node->count--;
            }

            int max_depth = 0;
            queue<pair<TrieNode*, int>> q;
            q.push({root, 0});
            while (!q.empty()) {
                auto [current_node, depth] = q.front();
                q.pop();
                for (auto& [char_, child] : current_node->children) {
                    if (child->count >= k) {
                        if (depth + 1 > max_depth) {
                            max_depth = depth + 1;
                        }
                        q.push({child, depth + 1});
                    }
                }
            }

            answer[i] = max_depth;

            for (TrieNode* node : path) {
                node->count++;
            }
        }

        return answer;
    }
};

int main() {
    Solution solution;
    vector<string> words1 = {"jump", "run", "run", "jump", "run"};
    int k1 = 2;
    vector<int> result1 = solution.longestCommonPrefix(words1, k1);
    for (int len : result1) {
        cout << len << " ";
    }
    cout << endl; // 输出应为 3 4 4 3 4

    vector<string> words2 = {"dog", "racer", "car"};
    int k2 = 2;
    vector<int> result2 = solution.longestCommonPrefix(words2, k2);
    for (int len : result2) {
        cout << len << " ";
    }
    cout << endl; // 输出应为 0 0 0

    return 0;
}